package kyssion.leetcode.num101_150;

public class code130_被围绕的区域 {

    public static void main(String[] args) {
        char[][] chars = new char[][]{
                {'O', 'X', 'X', 'O', 'X'},
                {'X', 'O', 'O', 'X', 'O'},
                {'X', 'O', 'X', 'O', 'X'},
                {'O', 'X', 'O', 'O', 'O'},
                {'X', 'X', 'O', 'X', 'O'}
        };
        char[][] chars1 = new char[][]{
                {'X', 'X', 'X', 'X'},
                {'X', 'O', 'O', 'X'},
                {'X', 'X', 'O', 'X'},
                {'X', 'O', 'X', 'X'}
        };
        //[["O","X","X","O","X"],["X","X","X","X","O"],["X","X","X","O","X"],["O","X","O","O","O"],["X","X","O","X","O"]]
        new code130_被围绕的区域().solve(chars1);
        System.out.println();
    }

    /**
     * 第一种想法先遍历横线的再遍历总向的,出现错误,无法实现途中的方法
     *
     * @param board
     */
    public void solve2(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        for (int a = 0; a < board.length; a++) {
            ans(board, a, true);
        }
        for (int a = 0; a < board[0].length; a++) {
            ans(board, a, false);
        }

        for (int a = 0; a < board.length; a++) {
            for (int b = 0; b < board[a].length; b++) {
                if (board[a][b] == 'I') {
                    board[a][b] = 'O';
                }
            }
        }
    }

    private void ans(char[][] chars, int index, boolean isRow) {
        int start = 0;
        int end = isRow ? chars[0].length - 1 : chars.length - 1;
        while (start <= end) {
            if (isRow && chars[index][start] == 'X' ||
                    !isRow && chars[start][index] == 'X') {
                break;
            }
            start++;
        }

        while (end >= start) {
            if (isRow && chars[index][end] == 'X' ||
                    !isRow && chars[end][index] == 'X') {
                break;
            }
            end--;
        }
        start++;
        end--;
        while (start <= end) {
            if (isRow) {
                if (chars[index][start] == 'I') {
                    chars[index][start] = 'X';
                } else if (chars[index][start] == 'O') {
                    chars[index][start] = 'I';
                }
            } else {
                if (chars[start][index] == 'I') {
                    chars[start][index] = 'X';
                } else if (chars[start][index] == 'O') {
                    chars[start][index] = 'I';
                }
            }
            start++;
        }
    }

    /**
     * 对边缘部分进行深度遍历
     *
     * @param board
     */
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        int l = board[0].length - 1;
        for (int a = 0; a < board.length; a++) {
            find(board, a, 0);
            find(board, a, l);
        }

        for (int a = 0; a < l; a++) {
            find(board, 0, a);
            find(board, board.length-1, a);
        }

        for (int a = 0; a < board.length; a++) {
            for (int b = 0; b < board[a].length; b++) {
                if (board[a][b] == 'I') {
                    board[a][b] = 'O';
                } else if (board[a][b] == 'O') {
                    board[a][b] = 'X';
                }
            }
        }
    }


    public void find(char[][] board, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length ||
                board[i][j] != 'O') {
            return;
        }
        board[i][j] = 'I';
        find(board, i - 1, j);
        find(board, i + 1, j);
        find(board, i, j - 1);
        find(board, i, j + 1);
    }
}